#include <vector>
#include <iostream>
#include <utility>

namespace ns_pq
{
    template<class T, class Container=std::vector<T>, class Compare = std::less<int>>
    class priority_queue
    {
    public:
        T& top()
        {
            return _con[0];
        }

        explicit priority_queue(const Compare& comp = Compare())
        : _cmp(comp) {}

        void pop()
        {
            std::swap(_con[0], _con[size() - 1]);
            _con.pop_back();
            adjust_down();
        }

        void push(const T& t)
        {
            _con.push_back(t);
            adjust_up();
        }

        int size()
        {
            return _con.size();
        }

        bool empty()
        {
            return _con.size() == 0;
        }

    private:
        void adjust_up()
        {
            int child = _con.size() - 1;
            while(child > 0)
            {
                int father = (child - 1) / 2;
                if(_cmp( _con[father], _con[child]))
                {
                    std::swap( _con[father], _con[child]);
                    child = father;
                }
                else
                    break;
            }
        }

        void adjust_down()
        {
            int father = 0;
            int left_child = 2 * father + 1;
            while(left_child < _con.size())
            {
                if(left_child + 1 < _con.size())
                {
                    if(_cmp(_con[left_child], _con[left_child + 1])) left_child++;
                }
                if(_cmp(_con[father], _con[left_child]))
                {
                    std::swap(_con[father], _con[left_child]);
                    father = left_child;
                    left_child = 2 * father + 1;
                }
                else
                    break;
            }
        }

    private:
        Container _con;
        Compare _cmp;
    };
}